#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=2048;
int read(){
    int f=1;int m=0;char c=getchar();
    while((c<'0'||c>'9')){if(c=='-')f=-1;c=getchar();}
    while(!(c<'0'||c>'9')){m=m*10+(c-'0');c=getchar();}
    return m*f;
}
int n;
ll a[maxn];
ll dp[maxn][maxn][3];
int l,r;
void solve(){
    n=read();
    if(n>2000){
        // cout<<"Oh No! ";
        int x;
        ll sum;n--;x=read();sum=x;
        while(n--){
            x=read();
            sum+=x;
        }sum/=2;
        cout<<sum<<'\n';
        return ;
    }
    for(int i=1;i<=n;i++){
        a[i]=read();
    }a[0]=-1;
    memset(dp,0,sizeof dp);
    for(int i=2;i<=n;i++){
        for(int j=i-2;j>=0;j--){
            if(a[j]==a[i]){
                dp[i][i-1][0]=max(dp[i][i-1][0],dp[i-1][j][1]+a[i]);
                dp[i][i-1][1]=max(dp[i][i-1][1],dp[i-1][j][0]+a[i]);
            }else {
                dp[i][i-1][0]=max(dp[i][i-1][0],dp[i-1][j][1]);
                dp[i][i-1][1]=max(dp[i][i-1][1],dp[i-1][j][0]);
            }
            if(a[i]==a[i-1]){
                dp[i][j][0]=max(dp[i][j][0],dp[i-1][j][0]+a[i]);
                dp[i][j][1]=max(dp[i][j][1],dp[i-1][j][1]+a[i]);
            }else {
                dp[i][j][0]=max(dp[i][j][0],dp[i-1][j][0]);
                dp[i][j][1]=max(dp[i][j][1],dp[i-1][j][1]);
            }
        }
        
    }
    ll ans=0;
    for(int i=0;i<=n;i++){
        ans=max(ans,dp[n][i][0]);
        ans=max(ans,dp[n][i][1]);
    }
    cout<<ans<<'\n';
}
int main(){
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    int T;
    T=read();
    while(T--){
        solve();
    }
    return 0;
}